package history.study.dynamic_programming;

// 213. 打家劫舍 II
// 1. dp[i]表示有i户人家时，最大收益是dp[i]
// 2. dp[i] = Math.max(dp[i-1], dp[i-2]+nums[i])
// 3. dp[0] = nums
public class LeetCode_213 {
    public static void main(String[] args) {
        System.out.println(rob(new int[]{1,2,1,1}));
    }
    public static int rob(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int length = nums.length;
        if (length == 1) return nums[0];
        if (length == 2) return Math.max(nums[0], nums[1]);;
        int [][]state = new int[2][2];
        state[0][0] = nums[0];
        state[0][1] = Math.max(nums[0], nums[1]);
        state[1][0] = nums[1];
        state[1][1] = Math.max(nums[1], nums[2]);

        //从第1家开始偷直到length-1家
        for (int i = 2; i < length-1; i++) {
            int temp = state[0][1];
            state[0][1] = Math.max(state[0][1], state[0][0] + nums[i]);
            state[0][0] = temp;
            System.out.println(String.format("state[0][%s] is %s", i, state[0][i]));
        }
        // 从第2家开始偷直到length家
        for (int i = 3; i < length; i++) {
            int temp = state[1][1];
            state[1][1] = Math.max(state[1][1], state[1][0] + nums[i]);
            state[1][0] = temp;
            System.out.println(String.format("state[1][%s] is %s", i, state[0][i]));
        }
        return Math.max(state[0][1], state[1][1]);
    }
}
